/*
 * @lc app=leetcode.cn id=198 lang=javascript
 *
 * [198] 打家劫舍
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  let length = nums.length
  if (length == 0) return 0
  if (length == 1) return nums[0]

  let dp = Array.from(new Array(length), () => new Array(length).fill(0))
  dp[0][0] = 0
  dp[0][1] = nums[0]

  for (let i = 1; i < length; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1])
    dp[i][1] = nums[i] + dp[i - 1][0]
  }

  return Math.max(dp[length - 1][0], dp[length - 1][1])
}
// @lc code=end

// 思路
// 相邻两房不能同时光顾，求能够偷的的最高金额，金额恒为正数
// 假设没有相邻禁偷限制，若想前n个房屋内偷到最高
// dp[n] = dp[n-1] + nums[n]
// 由此可想到斐波那契数列，从而想到动态规划解决
// DP动态规划
// 子问题(重复性)
// dp[i]：0~i 能偷到到的 max value
// dp[i] = dp[i-1] +nums[i]
// 状态定义
// 第i个偷
// dp[i][1]，增加维度，二维1代表偷当前i房
// 第i个不偷
// dp[i][0]，增加维度，二维0代表不偷当前i房
// DP方程
// 第i个不偷
// dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1])
// 不知道i-1是否能偷，偷也不违背相邻原则
// 第i个偷
// dp[i][1] = nums[i] + Math.max(dp[i-1][0]+0) = nums[i] + dp[i-1][0]
// 第i房偷，则先加nums[i]之金额，且第i-1就一定不能偷，否则违背相邻原则
// 至于dp[i-2]则不需重复考虑，因其已在dp[i-1]的子问题当中了
// 总结状态转移方程为
// dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]);
// dp[i][1] = dp[i-1][0] + nums[i];
